package com.example.algorithm.dualpointer;

/**
 * @author yuzhenxin
 * @date 2023/8/14
 */
public class RemoveNumber {

    public static void main(String[] args) {
        String input = "a1b2c3d4fse";
        System.out.println(removeNumber(input));
        System.out.println(removeNumberWithOrder(input));
    }

    /**
     * 移除字符串中的数字，时间复杂度O(n)，空间复杂度O(1)
     *
     * @param s 字符串
     * @return 移除数字后的字符串
     */
    private static String removeNumber(String s) {
        char[] chars = s.toCharArray();
        int i = 0;
        int j = chars.length - 1;
        while (i < j) {
            while (i < j && Character.isLetter(chars[i])) {
                i++;
            }
            while (i < j && !Character.isLetter(chars[j])) {
                j--;
            }
            if (i < j) {
                char temp = chars[i];
                chars[i] = chars[j];
                chars[j] = temp;
                i++;
                j--;
            }
        }
        return new String(chars).substring(0, Character.isLetter(s.charAt(i)) ? i + 1 : i);
    }

    /**
     * 移除字符串中的数字，时间复杂度O(n)，空间复杂度O(1)，且保持字母相对顺序不变
     *
     * @param s 字符串
     * @return 移除数字后的字符串
     */
    private static String removeNumberWithOrder(String s) {
        int i = 0;
        int j = s.length() - 1;
        while (i < j) {
            while (i < j && Character.isLetter(s.charAt(i))) {
                i++;
            }
            while (i < j && !Character.isLetter(s.charAt(j))) {
                j--;
            }
            if (i < j) {
                s = s.substring(0, i) // 都是字母
                        + s.substring(i + 1, j + 1) // 中间的
                        + s.charAt(i) // 前面换过来的数字
                        + s.substring(j + 1); // 都是数字
                i++;
                j--;
            }
        }
        return s.substring(0, Character.isLetter(s.charAt(i)) ? i + 1 : i);
    }
}
